package ali;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 215. 数组中的第K个最大元素：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
 * @author wxh
 */
public class Solution_6 {

	//解法1：基于java的PriorityQueue大顶堆排序完成
	public int findKthLargest(int[] nums, int k) {
		PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(nums.length, (a,b) -> b-a);
		for (int num : nums) {
			priorityQueue.offer(num);
		}
		//出来k-1个元素，剩下大顶堆的堆顶元素就是第k大元素了
		for (int i = 0; i < k -1; i++) {
			priorityQueue.poll();
		}
		return priorityQueue.poll();
	}

	// 解法2（性能更佳，推荐）：基于java的PriorityQueue小顶堆排序完成
	public int findKthLargest2(int[] nums, int k) {

		//维护一个大小为K的小顶堆
		PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(k);
		for (int i = 0; i < k; i++) {
			priorityQueue.offer(nums[i]);
		}

		for (int i = k; i < nums.length; i++) {
			//如果比堆顶元素大，就把堆顶元素删除，并且将这个元素插入到堆中
			if (nums[i] > priorityQueue.peek()) {
				priorityQueue.poll();
				priorityQueue.offer(nums[i]);
			}
		}
		return priorityQueue.poll(); //堆顶元素就是第k大元素
	}

	// 解法3：基于快速排序实现
//	public int findKthLargest3(int[] nums, int k) {
//
//	}

	public static void main(String[] args) {

		Solution_6 solution_6 = new Solution_6();
		System.out.println(solution_6.findKthLargest2(new int[] {3, 2, 1, 5, 6, 4}, 2));
	}

}